package com.south.base.test.arithmetic.dynamic.programming;

import org.junit.Assert;
import org.junit.Test;

import java.util.Arrays;
import java.util.List;

/**
 * @author Administrator
 * @date 2019/12/3 16:30
 */
public class Word {
    /**
     * 给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
     * 说明：
     * 拆分时可以重复使用字典中的单词。
     * 你可以假设字典中没有重复的单词。
     */
    @Test
    public void wordBreak() {
        Assert.assertTrue(wordBreak("leetcode", Arrays.asList("leet", "code")));
        Assert.assertTrue(wordBreak("applepenapple", Arrays.asList("apple", "pen")));
        Assert.assertFalse(wordBreak("catsandog", Arrays.asList("cats", "dog", "sand", "and", "cat")));
        Assert.assertTrue(wordBreak("cats", Arrays.asList("cat", "ca", "ts")));
        Assert.assertFalse(wordBreak("cats", Arrays.asList("cat", "c", "ts")));
    }

    public boolean wordBreak2(String s, List<String> wordDict) {
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && wordDict.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }

    public boolean wordBreak(String s, List<String> wordDict) {
        if (s.length() == 0) {
            return true;
        }
        boolean[] booleans = new boolean[s.length() + 1];
        booleans[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (String word : wordDict) {
                if (booleans[i - 1] && s.indexOf(word, i - 1) == i - 1) {
                    booleans[i + word.length() - 1] = true;
                }
            }
        }
        return booleans[s.length()];
    }
}
